//////////////////////////////////////////////////////
// 程序名称：用Liang-Barsky算法实现直线段裁剪
// 功 能：借助编写的平台实现线段裁剪
// 编译环境：Visual Studio 2017，EasyX_20190219(beta)
// 作 者：xyqlx<mxxyqlx@qq.com>
// 最后修改：2019-3-21
#include <conio.h>
#include <graphics.h>
#include <cmath>

COLORREF currentColor = RED;

void MPLline(int x1, int y1, int x2, int y2, COLORREF color)
{
	int a, b, d1, d2, d, x, y;
	if (x1 > x2)
	{
		x1 ^= x2;
		x2 ^= x1;
		x1 ^= x2;
		y1 ^= y2;
		y2 ^= y1;
		y1 ^= y2;
	}
	x = x2 - x1;
	y = y2 - y1;
	if (y >= x)
	{
		a = x1 - x2;
		b = y2 - y1;
		d = 2 * a + b;
		d1 = 2 * (a + b);
		d2 = 2 * a;
		x = x1;
		y = y1;
		putpixel(x, y, color);
		while (y < y2)
		{
			if (d < 0)
			{
				x++;
				y++;
				d += d1;
			}
			else
			{
				y++;
				d += d2;
			}
			putpixel(x, y, color);
		}
	}
	else if (y <= x && y >= 0)
	{
		a = y1 - y2;
		b = x2 - x1;
		d = 2 * a + b;
		d1 = 2 * (a + b);
		d2 = 2 * a;
		x = x1;
		y = y1;
		putpixel(x, y, color);
		while (x < x2)
		{
			if (d < 0)
			{
				x++;
				y++;
				d += d1;
			}
			else
			{
				x++;
				d += d2;
			}
			putpixel(x, y, color);
		}
	}
	else if (y >= -x)
	{
		a = y2 - y1;
		b = x2 - x1;
		d = 2 * a + b;
		d1 = 2 * (a + b);
		d2 = 2 * a;
		x = x1;
		y = y1;
		putpixel(x, y, color);
		while (x < x2)
		{
			if (d < 0)
			{
				x++;
				y--;
				d += d1;
			}
			else
			{
				x++;
				d += d2;
			}
			putpixel(x, y, color);
		}
	}
	else
	{
		a = x1 - x2;
		b = y1 - y2;
		d = 2 * a + b;
		d1 = 2 * (a + b);
		d2 = 2 * a;
		x = x1;
		y = y1;
		putpixel(x, y, color);
		while (y > y2)
		{
			if (d < 0)
			{
				x++;
				y--;
				d += d1;
			}
			else
			{
				y--;
				d += d2;
			}
			putpixel(x, y, color);
		}
	}
}

class Shape
{
  public:
	Shape(int n) : stateNum(n) {}
	virtual void Redraw() = 0;
	int stateNum;
	virtual void State(int state, int x, int y) = 0;
	virtual ~Shape(){};
};

class Line : public Shape
{
  public:
	int x1, y1, x2, y2;
	COLORREF lineColor;
	Line() : Shape(4) {}
	Line(int x1, int y1, int x2, int y2, COLORREF lineColor) : Shape(4), x1(x1), y1(y1), x2(x2), y2(y2), lineColor(lineColor) {}
	virtual void Redraw()
	{
		MPLline(x1, y1, x2, y2, lineColor);
	}
	virtual void State(int state, int x, int y)
	{
		switch (state)
		{
		case 1:
			x1 = x;
			y1 = y;
			break;
		case 2:
			x2 = x;
			y2 = y;
			lineColor = currentColor;
		case 3:
			MPLline(x1, y1, x2, y2, lineColor);
			break;
		}
	}
	virtual ~Line() {}
};

class SRectangle : public Shape
{
  public:
	int left, right, bottom, top;
	COLORREF lineColor;
	SRectangle() : Shape(4) {}
	SRectangle(int left, int right, int bottom, int top, COLORREF lineColor) : Shape(4), left(left), right(right), bottom(bottom), top(top), lineColor(lineColor) {}
	virtual void Redraw()
	{
		MPLline(left, top, right, top, lineColor);
		MPLline(left, top, left, bottom, lineColor);
		MPLline(left, bottom, right, bottom, lineColor);
		MPLline(right, bottom, right, top, lineColor);
	}
	virtual void State(int state, int x, int y)
	{
		switch (state)
		{
		case 1:
			left = x;
			top = y;
			break;
		case 2:
			right = x;
			bottom = y;
			lineColor = currentColor;
			Redraw();
			break;
		case 3:
			if (left > right)
			{
				int t = left;
				left = right;
				right = t;
			}
			if (bottom > top)
			{
				int t = bottom;
				bottom = top;
				top = t;
			}
			Redraw();
			break;
		}
	}
	virtual ~SRectangle() {}
};

//其实这里没有判断溢出的机制
Shape *shapes[10010];
Shape *currentShape;
int shapeIndex = 0;

//使用缓冲技术，减少因图形数量增加时出现的大量Redraw消耗
IMAGE img(640, 480);

void Refresh()
{
	SetWorkingImage();
	putimage(0, 0, &img, SRCCOPY);
}

//有生之年第一次在示例之外用到工厂函数（
class ShapeFactory
{
  public:
	//其实用枚举更好
	static int maxID;
	int shapeID = 1;
	void changeShape()
	{
		if (++shapeID > maxID)
		{
			shapeID = 1;
		}
	}
	Shape *createShape()
	{
		switch (shapeID)
		{
		case 1:
			return new Line();
		case 2:
			return new SRectangle();
		default:
			return new Line();
		}
	}
};
int ShapeFactory::maxID = 2;

//左裁剪框
SRectangle lclipRect(100, 200, 100, 200, GREEN);
//右裁剪框
SRectangle rclipRect(420, 520, 100, 200, GREEN);

//初始化画布和屏幕(现在已经是用来全部重绘的函数了)
void Init()
{
	//填充背景为白色
	SetWorkingImage(&img);
	setbkcolor(WHITE);
	cleardevice();

	for (int i = 0; i < shapeIndex; ++i)
	{
		if (shapes[i])
			shapes[i]->Redraw();
	}
	//画文字提示
	settextcolor(BLACK);
	moveto(5, 5);
	outtext(TEXT("left click to select startpoint"));
	moveto(5, 20);
	outtext(TEXT(" and endpoint in the left window"));
	SetWorkingImage();
	Refresh();
}

//清理函数（虽然似乎不会执行）
void Clear()
{
	for (int i = 0; i < shapeIndex; ++i)
	{
		delete shapes[i];
	}
}

bool L_B_LineClip(Line &line, const SRectangle &rect);

void CopyClipLine(const Line &line)
{
	Line *currentLine = new Line(line.x1 + 320, line.y1, line.x2 + 320, line.y2, line.lineColor);
	if (L_B_LineClip(*currentLine, rclipRect))
	{
		shapes[shapeIndex++] = currentLine;
		SetWorkingImage(&img);
		currentLine->Redraw();
		SetWorkingImage();
		currentLine->Redraw();
	}
	else
	{
		delete currentLine;
		currentLine = NULL;
	}
}

void Display(unsigned n)
{
	//计算
	float PI = float(acos(0) * 2);
	int *px = new int[n], *py = new int[n];
	for (int i = 0; i < n; i++)
	{
		px[i] = 100 + int(50 * cos(i * 2 * PI / n));
		py[i] = 100 + int(50 * sin(i * 2 * PI / n));
	}
	//绘图
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < i; ++j)
		{
			Line *line = new Line(px[i], py[i], px[j], py[j], BLUE);
			shapes[shapeIndex++] = line;
			SetWorkingImage(&img);
			line->Redraw();
			CopyClipLine(*line);
		}
	Refresh();
}

//主消息循环
void MessageLoop()
{
	MOUSEMSG msg;
	currentShape = new Line;
	int cnt = 0;
	ShapeFactory shapeFactory;

	//缺少说明，仅仅用于调试
	while (1)
	{
		msg = GetMouseMsg();
		switch (msg.uMsg)
		{
		case WM_MOUSEMOVE:
			if (cnt)
			{
				Refresh();
				if (currentShape)
					currentShape->State(cnt, msg.x, msg.y);
				else
					lclipRect.State(cnt, msg.x, msg.y);
			}
			break;
		case WM_LBUTTONDOWN:
			Refresh();
			currentShape->State(++cnt, msg.x, msg.y);
			if (++cnt >= currentShape->stateNum)
			{
				shapes[shapeIndex++] = currentShape;
				//复制并裁剪
				Line *currentLine = dynamic_cast<Line *>(currentShape);
				CopyClipLine(*currentLine);
				SetWorkingImage(&img);
				currentShape->Redraw();
				SetWorkingImage();
				currentShape = shapeFactory.createShape();
				cnt = 0;
			}
			Refresh();
			break;
		case WM_RBUTTONDOWN:
			if (currentShape)
			{
				currentColor = GREEN;
				cnt = 0;
				delete currentShape;
				currentShape = NULL;
			}
			Refresh();
			lclipRect.State(++cnt, msg.x, msg.y);
			if (++cnt >= lclipRect.stateNum)
			{
				//重绘并裁剪
				rclipRect = lclipRect;
				rclipRect.left += 320;
				rclipRect.right += 320;
				int currentShapeIndex = shapeIndex;
				for (int i = 0; i < currentShapeIndex; ++i)
				{
					if (shapes[i])
					{
						Line *line = dynamic_cast<Line *>(shapes[i]);
						if (line)
						{
							if (line->x1 > 320 || line->x2 > 320)
							{
								delete shapes[i];
								shapes[i] = 0;
							}
							else
							{
								CopyClipLine(*line);
							}
						}
					}
				}
				Init();
				currentShape = shapeFactory.createShape();
				currentColor = RED;
				cnt = 0;
			}
			Refresh();
			break;
		}
	}
}

int main()
{
	// 创建绘图窗口，大小为 640x480 像素
	initgraph(640, 480);
	//初始化
	//绘制分割线
	shapes[shapeIndex++] = new Line(320, 0, 320, 480, BLACK);
	//绘制裁剪框
	shapes[shapeIndex++] = &lclipRect;
	Init();
	//展示
	Display(7);
	//开始绘制
	MessageLoop();
	//结束绘制
	_getch();	 // 按任意键继续
	closegraph(); // 关闭绘图窗口
	Clear();
	return 0;
}

//以下是主要内容
bool L_B_LineClip(Line &line, const SRectangle &rect)
{
	int p1 = line.x1 - line.x2;
	int q1 = line.x1 - rect.left;
	int q2 = rect.right - line.x1;
	int p3 = line.y1 - line.y2;
	int q3 = line.y1 - rect.bottom;
	int q4 = rect.top - line.y1;
	double umax = 0, umin = 1;
	if (!p1)
	{
		if (q1 < 0 || q2 < 0)
			return 0;
		if(p3 < 0)
		{
			double u3 = double(q3) / p3,u4 = double(q4) / -p3;
			if(u3 > umax)
				umax = u3;
			if(u4 < umin)
				umin = u4;
		}
		else{
			double u3 = double(q3) / p3,u4 = double(q4) / -p3;
			if(u4 > umax)
				umax = u4;
			if(u3 < umin)
				umin = u3;
		}
	}
	else if(!p3){
		if (q3 < 0 || q4 < 0)
			return 0;
		if(p1 < 0)
		{
			double u1 = double(q1) / p1, u2 = double(q2) / -p1;
			if(u1 > umax)
				umax = u1;
			if(u2 < umin)
				umin = u2;
		}
		else{
			double u1 = double(q1) / p1, u2 = double(q2) / -p1;
			if(u2 > umax)
				umax = u2;
			if(u1 < umin)
				umin = u1;
		}
	}
	else{
		if(p3 < 0)
		{
			double u3 = double(q3) / p3,u4 = double(q4) / -p3;
			if(u3 > umax)
				umax = u3;
			if(u4 < umin)
				umin = u4;
		}
		else{
			double u3 = double(q3) / p3,u4 = double(q4) / -p3;
			if(u4 > umax)
				umax = u4;
			if(u3 < umin)
				umin = u3;
		}
		if(p1 < 0)
		{
			double u1 = double(q1) / p1, u2 = double(q2) / -p1;
			if(u1 > umax)
				umax = u1;
			if(u2 < umin)
				umin = u2;
		}
		else{
			double u1 = double(q1) / p1, u2 = double(q2) / -p1;
			if(u2 > umax)
				umax = u2;
			if(u1 < umin)
				umin = u1;
		}
	}
	if(umax > umin)
		return 0;
	int x1 = line.x1 + umax * (line.x2 - line.x1);
	int y1 = line.y1 + umax * (line.y2 - line.y1);
	line.x2 = line.x1 + umin * (line.x2 - line.x1);
	line.y2 = line.y1 + umin * (line.y2 - line.y1);
	line.x1 = x1;
	line.y1 = y1;
	return 1;
}